package first.niuke.midding;

/**
 * @ClassName NC87
 * @description:
 * @author: 荣燊
 * @create: 2021-06-26 13:27
 **/
public class NC87 {
    public static void main(String[] args) {

    }


    // 丢棋子问题,丢鸡蛋问题
    /**
     * 一座大楼有层，地面算作第0层，最高的一层为第N层。
     * 已知棋子从第0层掉落肯定不会摔碎，从第i层掉落可能会摔碎，
     * 也可能不会摔碎。给定整数N作为楼层数，再给定整数K作为棋子数，
     * 返回如果想找到棋子不会摔碎的最高层数，即使在最差的情况下扔的最小次数。
     * 一次只能扔一个棋子。
     */

    /**
     * 每次扔的位置都是最佳的，i个棋子扔time次，
     * 第1次时，如果碎了，向下可以探测“i-1个棋子扔time-1次”层；
     * 如果没碎，向上可以探测“i个棋子扔time-1次”层。
     * 上下层数加当前1层即为i个棋子扔time次能探测的最大层数
     */

    /**
     * 递归法： dp[N][K]:表示k个棋子测试N层的的最小次数
     *     dp[0][K] = 0,
     *     dp[N][1] = N, // 一枚棋子那么你只能从第一层开始一层层抛
     *
     *     // 两种情况：
     *     // 1.当在第i层抛时，第一枚棋子没碎，那么下一步只要在第i~n层再抛棋子就可以了
     *     // 2.当在第i层抛时，第一枚棋子碎了，棋子数减1，那么你只要在0~i-1层继续抛就可以
     *     dp[N][K] = min( max(dp[i-1][K-1], dp[N-i][K])) + 1
     */

    public int solve (int n, int k) {
        // write code here
        if (n<1 || k<1) {
            return 0;
        }

        // 表示1个棋子，那么就需要一层层测试
        if (k == 1) {
            return n;
        }

        int[][] dp = new int[n+1][k+1];

        // 1个棋子，i层
        for (int i=1; i< dp.length; i++) {
            dp[i][1] = i;
        }

        for (int i=1; i<dp.length; i++) { //i层
            for (int j=2; j<=k; j++) { // j个棋子

                int min = Integer.MAX_VALUE;

                // 从第m层抛，
                for (int m=1; m<i+1; m++) {
                    // dp[m-1][j-1], dp[i-k][j] 的最大值?????
                    min = Math.min(min, Math.max(dp[m-1][j-1], dp[i-m][j]));
                }

                dp[i][j] = min + 1;
            }
        }
        return dp[n][k];

    }
}
